Greed Law Proof Patterns
Greedy method of selecting in a certain order
Show that replacing the slower order with the faster order does not decrease the score you want to maximize
Show advancedness. Indicates the best method at a given "point in time" in "chronological" order.
Imposing properties that can be assumed for the optimal solution (this form etc. since it is not worse if we replace two of them), we show that it is greedy.
・Selection that can be optimal for each operation (meaning that there exists an optimal solution that includes that selection).
・After each operation, it can be attributed to a smaller-scale problem, and the solution can be obtained recursively.
・The proof is basically a backward reasoning, assuming that all optimal solutions do not include "selection by greed" and showing a contradiction.
ex.)Interval scheduling
Show at time 0. Let I=[L,R] be one of the ones with the smallest R, and assume that all optimal solutions do not contain I. If we take one of the optimal solutions (it is clear that there is an optimal solution) and let J=[L',R'] be the one with the smallest R, J is contradicted by the fact that J is always replaced by I. Therefore, I may be adopted.
In this way, the phrase "no loss" that we often see in proof of greed does not appear.
First, show the lower boundary
Showing agreement with the lower boundary
Therefore, it is the optimal solution
---
This page is auto-translated from /nishio/貪欲法の証明パターン. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.